package algorithm.leetcode.difficulty;

/*
 老师想给孩子们分发糖果，有 N 个孩子站成了一条直线，老师会根据每个孩子的表现，预先给他们评分。
 你需要按照以下要求，帮助老师给这些孩子分发糖果：
 每个孩子至少分配到 1 个糖果。
 相邻的孩子中，评分高的孩子必须获得更多的糖果。
 那么这样下来，老师至少需要准备多少颗糖果呢？
 */

import java.util.Arrays;

/**
 * @author jack.wu
 * @version 1.0
 * @date 2020/12/24
 */
public class Question135 {

    public static void main(String[] args) {
        int[] ratings = {1, 0, 2};
        Question135 question = new Question135();
        int candy = question.candy(ratings);
        System.out.println(candy);

    }

    public int candy(int[] ratings) {
        if (ratings == null || ratings.length == 0) {
            return 0;
        }
        int len = ratings.length;
        int[] left = new int[len];
        int[] right = new int[len];

        Arrays.fill(left, 1);
        Arrays.fill(right, 1);

        for (int i = 1; i < len; i++) {
            if (ratings[i] > ratings[i - 1]) {
                left[i] = left[i - 1] + 1;
            }
        }

        int count = left[len - 1];
        for (int j = len - 2; j >= 0; j--) {
            if (ratings[j] > ratings[j + 1]) {
                right[j] = right[j + 1] + 1;
            }
            count += Math.max(left[j], right[j]);
        }
        return count;

    }
}
